package com.datastructure.linkedlist;

/**
 * @author: 临晖
 * @date: 2023/10/11
 * @description:
 */

/**
 * 链表相交
 */
public class Solution05 {


    /**
     *
     * 思路：首先计算出每个链表的长度，然后计算出俩个链表的差值，这个时候（例如相差n个节点），
     * 这个时候，从长的的第n个节点和短的节点的第一个节点同时开始遍历，如果相等则返回当前节点
     * 否则返回null；
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0;
        int sizeB = 0;

        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while (nodeA != null) {
            sizeA++;
            nodeA = nodeA.next;
        }

        while (nodeB != null) {
            sizeB++;
            nodeB = nodeB.next;
        }

        nodeA = headA;
        nodeB = headB;


        if (sizeA > sizeB) {
            for (int i = 0; i < sizeA - sizeB; i++) {
                nodeA = nodeA.next;
            }
        } else {
            for (int i = 0; i < sizeB - sizeA; i++) {
                nodeB = nodeB.next;
            }
        }


        while (nodeA != null && nodeB != null) {
            if (nodeA == nodeB) {
                return nodeA;
            }

            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }

        return null;




    }
}
